home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / Hack / UNIX / FSORT_C.ZIP / FSORT_C
Text File  |  1996-06-23  |  3KB  |  168 lines
  1. /* fsort.c -- sort files according to depth. 
  2.  *
  3.  * Read a list of files from stdin and sort them so that most shallow
  4.  * filenames come first.  That is, given the list of files
  5.  *
  6.  *      a/b
  7.  *      a
  8.  *      a/b/c/d
  9.  *      a/b/c
  10.  *
  11.  * this program will output
  12.  *
  13.  *      a
  14.  *      a/b
  15.  *      a/b/c
  16.  *      a/b/c/d
  17.  * 
  18.  * No other sorting is done (e.g. alphabetic).  Sorting is done based
  19.  * purely on the number of `/' characters in each pathname.
  20.  * It is easy enough to change the sorting criteria by changing the
  21.  * definition of qcmp below. 
  22.  * WARNING: Since this program uses quicksort, it does not sort stably.
  23.  */
  24.  
  25. #include <stdio.h>
  26.  
  27. char *malloc ();
  28. char *strchr ();
  29.  
  30. int qcmp ();
  31. char *xmalloc ();
  32.  
  33. struct node 
  34.   {
  35.     char *str;
  36.     struct node *next;
  37.   };
  38.  
  39. int
  40. main (argc, argv)
  41.      int argc;
  42.      char **argv;
  43. {
  44.   struct node root, *p, *q;
  45.   char l[255], **s, *newline;
  46.   int t, i;
  47.  
  48.   p = q = &root;
  49.   p->str = NULL;
  50.   p->next = NULL;
  51.   t = 0;
  52.  
  53.   while (fgets (l, 254, stdin))
  54.     {
  55.       if (newline = strchr (l, '\n'))
  56.         *newline = '\0';
  57.  
  58.       q = (struct node *) xmalloc (sizeof (struct node));
  59.       q->str = (char *) xmalloc ((strlen (l) + 1) * sizeof (char));
  60.       strcpy (q->str, l);
  61.       q->next = NULL;
  62.  
  63.       p->next = q;
  64.       p = q;
  65.       t++;
  66.     }
  67.  
  68.   p = &root;
  69.   s = (char **) xmalloc (t * sizeof (char *));
  70.   i = 0;
  71.   while (p = p->next)
  72.     s[i++] = p->str;
  73.  
  74.   qs_sort (s, t, qcmp);
  75.   for (i = 0; i < t; i++)
  76.     puts (s[i]);
  77.  
  78.   return 0;
  79. }
  80.  
  81. int 
  82. qcmp (a, b)
  83.      char *a, *b;
  84. {
  85.   int an, bn;
  86.   char *s;
  87.  
  88.   an = bn = 0;
  89.  
  90.   while (s = strchr (a, '/'))
  91.     {
  92.       an++;
  93.       a = s + 1;
  94.     }
  95.  
  96.   while (s = strchr (b, '/'))
  97.     {
  98.       bn++;
  99.       b = s + 1;
  100.     }
  101.  
  102.   if (an < bn)
  103.     return -1;
  104.   if (an > bn)
  105.     return 1;
  106.   return 0;
  107. }
  108.  
  109. char *
  110. xmalloc (size)
  111.      int size;
  112. {
  113.   char *message = "xmalloc: out of memory.\n"; 
  114.   char *p;
  115.  
  116.   p = (char *) malloc (size);
  117.  
  118.   if (p == NULL)
  119.     {
  120.       write (2, message, sizeof (message));
  121.       exit (1);
  122.     }
  123.  
  124.   return p;
  125. }
  126.  
  127.  
  128. qs_sort (base, count, func)
  129.      char *base[];
  130.      int count;
  131.      int (*func) ();
  132. {
  133.   qs_internal (base, 0, count - 1, func);
  134. }
  135.  
  136. qs_internal (base, left, right, func)
  137.      char *base[];
  138.      int left, right;
  139.      int (*func) ();
  140. {
  141.   int i, j;
  142.   char *x, *y;
  143.  
  144.   i = left;
  145.   j = right;
  146.   x = base[(left + right)/2];
  147.  
  148.   do 
  149.     {
  150.       while ((*func) (base[i], x) < 0 && i < right) i++;
  151.       while ((*func) (base[j], x) > 0 && j > left) j--;
  152.       if (i <= j)
  153.         {
  154.           y = base[i];
  155.           base[i] = base[j];
  156.           base[j] = y;
  157.           i++;
  158.           j--;
  159.         }
  160.     }
  161.   while (i <= j);
  162.  
  163.   if (left < j)
  164.     qs_internal (base, left, j, func);
  165.   if (i < right)
  166.     qs_internal (base, i, right, func);
  167. }
  168.